The present invention is related to wireless communication and, particularly, to the task of resource allocation for transmitter/receiver nodes in a wireless network.
Reference is made to the problem of finding an efficient proportional fair rate assignment, denoted by the vector of transmission rates r=[r1, . . . , rK]TεR+K, for the set of users K, in the coverage area of the network.
            maximize      r        ⁢                  ⁢                  ∑                  k          ∈          K                                              ⁢              log        ⁢                                  ⁢                  r          k                                subject      ⁢                          ⁢      to      ⁢                          ⁢      r        ∈    R  
The rate assignment for the users in the network is illustrated in FIG. 2. The interdependence of the user rates is described by an achievable rate region R, which is assumed to be a convex set. The rate region R is constituted by the physical layer techniques, for example MIMO transmission, and the channel realizations. It is well known that this problem can be solved by dual decomposition, [1]. The dual problem can be solved by a primal-dual algorithm, as described in the Algorithm illustrated in FIG. 5.
In order to allow for real time implementation of the algorithm its convergence speed and complexity is a main issue. The computational complexity of the Algorithm is dominated by the complexity to solve the Weighted Sum-Rate optimizationc*i=argmaxcεR{λiTc}, carried out in each iteration. Additionally when users in a network with more than one base station are coordinated each iteration causes signalling overhead among the base stations. As the complexity for solving the Weighted Sum-Rate optimization is constant for each iteration a main issue is to reduce the number of iterations necessitated to find the solution, or a rate configuration that is provable within a factor ε of the solution. The number of iterations needed depends on the update method for the dual variables and most frequently used methods for the update of the dual variables are
Subgradient Methods, are the most popular update rules, see for example, as they have a simple closed form expression for the update,
      λ          i      +      1        =                    [                              λ            i                    +                                    τ              i                        ⁢                          (                                                r                  i                  *                                -                                  c                  i                  *                                            )                                      ]            +        .  
The drawback of subgradient methods however is the poor convergence, especially in case high accuracy is necessitated.
Cutting Plane Methods, build on the fact that the dual function is convex and can therefore be lower bounded by hyperplanes. Iteratively hyperplanes are used to cut off halfspaces of points from the candidate points until the solution is found.
Ellipsoid Method [2] use Ellipsoids that contain the candidate points. Iteratively the Ellipsoid is cut into two half-ellipsoids and one is discarded. As an update the center of a new ellipsoids containing the remaining half ellipsoid is used. The new center λi+1 is calculated by
      g    =                  (                              r            i            *                    -                      c            i            *                          )                                                        (                                                r                  i                  *                                -                                  c                  i                  *                                            )                        T                    ⁢                                    A              i                              -                1                                      ⁡                          (                                                r                  i                  *                                -                                  c                  i                  *                                            )                                                      λ              i        +        1              =                  [                              λ            i                    +                                    1                              K                +                1                                      ⁢                          A              i                              -                1                                      ⁢            g                          ]            +                  A              i        +        1                    -        1              =                            K          2                                      K            2                    -          1                    ⁢              (                              A            i                          -              1                                -                                    2                              k                +                1                                      ⁢                          A              i                              -                1                                      ⁢                          gg              T                        ⁢                          A              i                              -                1                                                    )            
Kelley's Cutting Plane Method [3], approximates the dual function by hyperplanes and uses the minimizer of the linear approximation as an update. The new dual variables are the solution of the following optimization problem
            maximize              λ        ,        z              ⁢                  ⁢    z                                subject          ⁢                                          ⁢          to          ⁢                                          ⁢          z                ≥                              d            ⁡                          (                              λ                j                            )                                -                                    λ              ⁡                              (                                                      r                    j                    *                                    -                                      c                    j                    *                                                  )                                      ⁢                          ∀              j                                          =      0        ,    …    ⁢                  ,    i        λ    ≥    0.  
Various variants of adding hyperplanes to the linear approximation exist. Additionally, a method is considered, which is named Multi-Cut, where one hyperplane per user is added in each iteration. The Multi-Cut method drastically improves the convergence speed, however the costs for the dual update increases largely in each iteration.
Aitken's method [4] adds an acceleration mode to subgradient methods, resulting in faster convergence, however stability of the algorithm becomes an issue. The update rule calculates one subgradient step, thereby finding an intermediate dual vector
      λ    ~    =                    [                              λ            i                    +                                    τ              i                        ⁢                          (                                                r                  i                  *                                -                                  c                  i                  *                                            )                                      ]            +        .  With the intermediate dual vector one can compute{tilde over (r)}=argmaxr≧0{U(r)−{tilde over (λ)}Tr}, and{tilde over (c)}=argmaxcεR{{tilde over (λ)}Tc}to obtain a further sub-gradient step
      λ    ^    =                    [                              λ            ~                    +                                    τ              i                        ⁢                          (                                                r                  ~                                -                                  c                  ~                                            )                                      ]            +        .  Finally, use {tilde over (λ)} and {circumflex over (λ)} to compute
      λ                  i        +        1            ,      k        =            λ      k        -                                        (                                                            λ                  ~                                k                            -                              λ                k                                      )                    2                                                    λ              ^                        k                    -                      2            ⁢                                          λ                ~                            k                                +                      λ            k                              .      
One can observe that convergence speed is improved when more computational complexity is invested for the dual update. Some methods have closed form expressions for the update, while others necessitate to solve an optimization problem. The complexity and the convergence speed is summarized in FIG. 8.
As one can see, the state-of-the-art methods have either high complexity to calculate the dual update or suffer from poor convergence which again is computationally complex, due to the large number of Weighted Sum-Rate problems that need to be solved.
U.S. 2009/232074 A1 discloses an auction-based resource allocation in wireless systems. Systems and methods to assign one or more resources in a multi-user cellular Orthogonal Frequency-Division Multiple Access (OFDMA) uplink include specifying a resource allocation problem for one or more resources; converting the resource allocation problem into an assignment problem; solving the assignment problem through an auction; and allocating one or more resources to cellular users to maximize a system utility.